package double_pointer;

/**
 * @Description 42. 接雨水
 * @Author Firenut
 * @Date 2023-05-01 22:32
 * 思路: 计算每个列的盛水容量,最后相加起来
 */
public class T42_trap {
    // 法2: 双指针(优化空间复杂度)
    // 时间复杂度 O(n) 空间复杂度 O(1)
    public int trap(int[] height) {
        int sum = 0;
        int left = 1, right = height.length - 2;
        int left_max = 0, right_max = 0;
        // 这里的i可以简单的理解为循环的次数
        for (int i = 1; i <= height.length - 2; i++) {
            // 假设一开始height[left-1]大于height[right+1],则之后right会一直向左移动，直到height[left-1]大于height[right+1]。
            // 在这段时间内right所遍历的所有墙都是左侧最高点left_max 大于右侧最高点 right_max 的
            // 所以只需要 判断right_max与当前高度的关系,计算水的容量 (计算水容量时，高度看的是矮的一端,不会受right_max的影响)
            // 反之left右移，所经过的点只要判断left_max与当前高度的关系就行

            // 因为一开始left和right都是从两测向中心移动，所以记录到的left_max、right_max
            // 也就满足当前cur位置 左边最大和右边最大
            // 然后需要比较左右两侧谁大谁小，记较小的墙为less
            // 取小的一侧less,与当前位置比较大小，
            // 1.如果当前位置cur比less小,则可以注入的水为 less-cur
            // 2.如果当前位置cur比less大，则当前列没法注入水
            // 3.如果当前位置cur等于less,同样没法注入水

            if (height[left - 1] < height[right + 1]) {
                // left指针从左往右扫,判断并更新left_max
                left_max = Math.max(height[left - 1], left_max);

                if (left_max > height[left]) {
                    // 左边墙的最大高度 比当前高度大
                    sum += (left_max - height[left]);
                }
                left++;
            } else {
                // right指针从右往左扫,判断并更新right_max
                right_max = Math.max(right_max, height[right + 1]);

                if (right_max > height[right]) {
                    // 右边墙的最大高度比 当前高度大
                    sum += (right_max - height[right]);
                }
                right--;
            }
        }
        return sum;
    }

    // 法1: 动态规划
    // 时间复杂度: O(n) 空间复杂度: O(n)
    public int trap1(int[] height) {
        int sum = 0;
        // left_max[i] 表示i左边的墙的最大高度(不包括i); right_max[i] 表示i右边的墙的最大高度
        int[] left_max = new int[height.length];
        int[] right_max = new int[height.length];
        for (int i = 1; i < height.length - 1; i++) {
            left_max[i] = Math.max(left_max[i - 1], height[i - 1]);
        }
        for (int i = height.length - 2; i >= 1; i--) {
            right_max[i] = Math.max(right_max[i + 1], height[i + 1]);
        }
        for (int i = 1; i < height.length - 1; i++) {
            int min = Math.min(left_max[i], right_max[i]);
            if (min > height[i]) {
                sum += (min - height[i]);
            }
        }
        return sum;
    }
}
